//
//  Problem1039.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/11.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1039. 多边形三角剖分的最低得分 【动态规划】【切三角】
 给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

 假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

 返回多边形进行三角剖分后可以得到的最低分。

 示例 1：
     输入：[1,2,3]
     输出：6
     解释：多边形已经三角化，唯一三角形的分数为 6。
 示例 2：
     输入：[3,7,4,5]
     输出：144
     解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
 示例 3：
     输入：[1,3,1,4,1,5]
     输出：13
     解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
 提示：
     3 <= A.length <= 50
     1 <= A[i] <= 100
 */
@objcMembers class Problem1039: NSObject {
    func solution() {
        print(minScoreTriangulation([3,7,4,5]))
        
        print(minScoreTriangulation([1,3,1,4,1,5]))
    }
    
    /*
     动态规划
     1: 创建一个二位数组 dp[len][len] value[len]
     2: 三角形先确定了一个边（2个点），然后，计算另外一个点
     3: [1,3,1,4,1,5]， 以最后一个和第一个组成一个边：是(5,1)，那么另外一个点就有可能是剩下的任何点
        是dp[2] = 5*1*3 + dp[2][0]
        是dp[3] = dp[0][2] + 5*1*1 + dp[2][0]
        是dp[4] = dp[0][3] + 5*1*4 + dp[3][0]
        ....
     */
    func minScoreTriangulation(_ values: [Int]) -> Int {
        if values.count == 3 {          // 特例
            return values.reduce(1) { (first, second) -> Int in
                return first * second
            }
        }
        
        var dp = Array(repeating: Array(repeating: Int.max, count: values.count), count: values.count)
        let value = minScoreTriangulationDP(values, &dp, 0, values.count - 1)
        
        return value
    }
    
    func minScoreTriangulationDP(_ values: [Int], _ dp: inout [[Int]], _ start: Int, _ end: Int) -> Int {
        var lastNum = 0
        if end > start  {   // 0 1 2 3 4 5 6
            lastNum = end - start + 1
        } else {
            lastNum = values.count - 1 - start + 1 + start + 1
        }
        
        if dp[start][end] != Int.max {
            return dp[start][end]
        }
        
        if lastNum == 3 {       // 特例：就一个三角形
            dp[start][end] = getScore(values, start)
        } else {
            let value = values[start] * values[end]
            for i in start+1..<end {
                if i == start + 1 {
                    dp[start][end] = min(dp[start][end], value * values[i] + minScoreTriangulationDP(values, &dp, i, end))
                } else if i == end - 1 {
                    dp[start][end] = min(dp[start][end], value * values[i] + minScoreTriangulationDP(values, &dp, start, i))
                } else {
                    dp[start][end] = min(dp[start][end], value * values[i] + minScoreTriangulationDP(values, &dp, start, i) + minScoreTriangulationDP(values, &dp, i, end))
                }
            }
        }
        
        return dp[start][end]
    }
    
    func getScore(_ values: [Int], _ start: Int) -> Int {
        var value = values[start]
        if values.count - 1 == start {
            value *= values[0]
            value *= values[1]
        } else if values.count - 2 == start {
            value *= values[values.count - 1]
            value *= values[0]
        } else {
            value *= values[start+1]
            value *= values[start+2]
        }

        return value
    }
}
